package sort;

public class Seven_sort {

    public static void main(String[] args) {
        int[] arr = {10,5,13,20,1,25,7};
        heapSort(arr);
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    //堆排序
    //先将数组堆化
    //后交换
    //再堆化

    /**
     * 空间复杂度:原地交换O(1)
     * 时间复杂都:O(nlongn)
     * @param arr
     */
    public static void heapSort(int[] arr){
        //先堆化
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            siftDown(arr,i,arr.length);
        }
        for (int i = arr.length-1; i >0 ; i--) {
            swap(arr,0,i);//交换
            siftDown(arr,0,i);//再堆化
        }
    }

    private static void siftDown(int[] arr, int i,int length) {

        while (2*i+1<length){//还有左子树
            int j = 2*i+1;
            if(j+1<length&&arr[j]<arr[j+1]){
                j = j+1;
            }
            if(arr[i]<arr[j]){
                swap(arr,i,j);
                i = j;
            }else {
                break;
            }
        }

    }

    private static void swap(int[] arr,int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
